\documentclass[a4paper, 10pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage{makeidx}
\usepackage{fancyhdr}
\usepackage{fancyvrb}
\usepackage{graphicx}
\usepackage{multicol}
\usepackage{textcomp}
\usepackage{alltt}
\usepackage{times}
\usepackage{listings}
\usepackage{multirow}

\lstset{language=C,
  basicstyle=\footnotesize,        % the size of the fonts that are used for the code
  breakatwhitespace=false,         % sets if automatic breaks should only happen at whitespace
  breaklines=true,                 % sets automatic line breaking
  captionpos=b,                    % sets the caption-position to bottom
  escapeinside={\%*}{*)},          % if you want to add LaTeX within your code
  extendedchars=true,              % lets you use non-ASCII characters; for 8-bits encodings only, does not work with UTF-8
  frame=single,                    % adds a frame around the code
  keepspaces=true,                 % keeps spaces in text, useful for keeping indentation of code (possibly needs columns=flexible)
%  morekeywords={*,...},            % if you want to add more keywords to the set
  numbers=none,                    % where to put the line-numbers; possible values are (none, left, right)
  numbersep=5pt,                   % how far the line-numbers are from the code
%  numberstyle=\tiny\color{mygray}, % the style that is used for the line-numbers
%  rulecolor=\color{black},         % if not set, the frame-color may be changed on line-breaks within not-black text (e.g. comments (green here))
  showspaces=false,                % show spaces everywhere adding particular underscores; it overrides 'showstringspaces'
  showstringspaces=false,          % underline spaces within strings only
  showtabs=false,                  % show tabs within strings adding particular underscores
  stepnumber=1,                    % the step between two line-numbers. If it's 1, each line will be numbered
%  stringstyle=\color{mymauve},     % string literal style
  tabsize=2,                       % sets default tabsize to 2 spaces
%  title=\lstname                   % show the filename of files included with \lstinputlisting; also try caption instead of title
}


%% \fvset{fontfamily=helvetica}
%% \fvset{fontsize=\tiny}
\fvset{fontsize=\small}


\begin{document}
\title{Safe array handling for C}
\author{Jens Harms $<au1064@gmail.com>$}
\maketitle

This paper describes a standard library for safe array handling which uses handles (integer, like a file handle).
The library makes most C programs better to
understand, easier to write, easier to maintain, shorter and less
error prone. If he uses handles, the programmer can avoid the use of
pointer in a large part.  This library is compatible to the common
libc and does not force the programmer to implement new concepts. It
is extreme lightweight.  It provides lots of interessting new
possibilities.

\DefineShortVerb{\`}

% Die Lib. MLS verwaltet Listen (Arrays) einfach und sicher.
% Als Besonderheit wird zu jedem Array die Anzahl
% der belegten Plätze gespeichert.
% Dieser Zähler wird durch die Funktionen
% `m_put`, `m_setlen` ,`m_ins`, `m_del`, `m_write`, `m_clear` verändert.

The libraries name is MLS and it provides easy and safe Array handling.
If you work with arrays you will need three objects: a base ptr, a cursor and the length of the array. The programmer can access those object by a single integer (handle). MLS treats the allocated length of the array and the
used length of the array differently.
The used size of the array is manipulated by these functions:
`m_put`, `m_setlen` ,`m_ins`, `m_del`, `m_write`, `m_clear`.
The {\bf resize is done automatically}. If you increase the length of the array by one, it will be increased by factor 1.5. For any other value it will be resized to fit. The {\bf handle does not change} on resize, so its safe to have references to this array in different parts of your programm.

% Mit MLS kann nur auf belegte Plätze das Arrays zugegriffen
% werden, unabhängig von dem tatsächlichen allokierten Speicher.
% Mit `m_len` erhält man die Länge des belegten Teils des Arrays.
% Mit `m_bufsize` die tatsächlich Länge des Arrays.
You need to use `void *mls(int m, int pos)` to access memory inside
the array. It returns a pointer to the object at `pos` inside the
array `m`. Access outside of the used size of the array, will result
in an error message, telling you what you did, where you allocated the
array, where the error happened and, of course, the program is
terminated.  The returned pointers are only guaranteed to be valid
until the next operation that changes the length of the array.

With `int m_create(len,size)` you allocate an array. It returns a
handle to the array. The handle does not change if the array is
resized and its allways greater than zero. This is a really nice
feature. How can you implement a array of a array of struct T inside a
structure in C? Solution: it is an `int`. You do not need pointers,
typedefs or braces. In fact {\bf you can eleminate most of your
  pointers inside your programs}.

\newpage

\section{examples}
The getline functions demonstrates the basic principle of MLS.  But do
not confuse MLS with a string library. MLS handles arrays of any type
and reduces the need for pointers, thus making your programs smarter
and more safe. The function `m_putc(m,0)` is used as shortcut for
`char c=0; m_put(m,&c);`
%% ---------------------------------------------------------
\begin{lstlisting}[frame=single]
int getline(int buf, FILE *fp)
{
  int ch;
  m_clear(buf);
  while(1) {
    ch=fgetc(fp);
    if( ch <= 0 || ch==10 ) { m_putc(buf,0); return ch; }
    m_putc(buf,ch);
  }
}
\end{lstlisting}
%% ---------------------------------------------------------

The next example uses the new getline function. It reads
a ascii file containing numbers.
Again, {\bf no pointers are needed}\footnote{except for strtof}.

%% ---------------------------------------------------------
\begin{lstlisting}[frame=single]
int table_read(FILE *fp)
{
  char *ep;
  int buf= m_create(100,1);
  float data;
  int table = m_create( 100, sizeof(float) );
  while( !feof(fp) ) {
    if( getline(buf,fp) > 0 ) {
        data = strtof(m_buf(buf),&ep,0);
        if( *ep == 0 ) m_put(table,&data);
    }
  }
  m_free(buf);
  return table;
}
\end{lstlisting}
%% ---------------------------------------------------------

Very often i need a loop to go through all objects in an array.
This task is simplified by this precompiler macro:
\begin{verbatim}
#define m_foreach(lst,index,ptr) \
for(index=-1; m_next(lst,&index,&ptr); )
\end{verbatim}
The `ptr` is guaranteed to point to an object inside the array.
So the {\bf use of `*d` is safe!}.


%% ---------------------------------------------------------
\begin{lstlisting}[frame=single]

int table_write(int table, FILE *fp)
{
  int p; float *d;
  m_foreach(table,p,d) fprintf(fp,\"%f\n", *d);
}
\end{lstlisting}
%% ---------------------------------------------------------


Sometimes you have to deal with array of strings. The next example
scans a string for numbers. The function `m_free_strings` first frees
the allocated strings and than frees the given list.
%% ---------------------------------------------------------

\noindent\begin{minipage}[t]{.45\textwidth}
\begin{lstlisting}[frame=single]
int main()
{
  m_init();
  int p;
  char **match;
  char *str =
    "Hello-123-World-456-Test"
    "-789-EOT";
  int m = m_regex(0,
    ".*-([0-9]*)-.*-([0-9]*)-"
    ".*-([0-9]*)-",
    str );
  m_foreach(m,p,match)
    printf("SSTR %d: %s\n",p, *match );
  m_free_strings(m,0);
  m_destruct();
  return 0;
}
\end{lstlisting}
\end{minipage}\hfill
\begin{minipage}[t]{.5\textwidth}
\begin{Verbatim}[frame=topline,framesep=4mm,label=Output]
SSTR 0: Hello-123-World-456-Test-789-
SSTR 1: 123
SSTR 2: 456
SSTR 3: 789
\end{Verbatim}
\end{minipage}

The next examples shows how to break a string into some
substrings. If the last argument of `m_split` is 1, it will
remove leading spaces in the returned substrings.

\noindent\begin{minipage}[t]{.6\textwidth}
\begin{lstlisting}[frame=single]              ]
#include "mls.h"

int main()
{
  m_init();
  int p;
  char **match;
  char *str =
    "Hello-123-World-456-Test-789-EOT";
  int m = m_split(0,str,'-',1);
  m_foreach(m,p,match)
    printf("SSTR %d: %s\n",p, *match );
  m_free_strings(m,0);
  m_destruct();
  return 0;
}
\end{lstlisting}

\end{minipage}\hfill
\begin{minipage}[t]{.35\textwidth}
\begin{Verbatim}[frame=topline,framesep=4mm,label=Output]
SSTR 0: Hello
SSTR 1: 123
SSTR 2: World
SSTR 3: 456
SSTR 4: Test
SSTR 5: 789
SSTR 6: EOT
\end{Verbatim}
\end{minipage}
%% ---------------------------------------------------------


\section{Architecture}
The library has three layers (see figure \ref{fig:Architecture}).
The LST part contains the low-level memory management and the
array handling. The MLS part encapsulates the LST part and maps array handles to array pointers. The MLS\_DEBUG part is only compiled if MLS\_DEBUG is defined. This part overrides the functions in the MLS part and stores debug information to trace the MLS calls. The MISC part is for everything else.

\begin{figure}\caption{Architecture}
\centering
\includegraphics[width=0.4\textwidth]{archi.eps}
\label{fig:Architecture}
\end{figure}




\begin{figure}
\caption{Compare mls with libc standard}
\begin{tabular}{|l|l|}
\hline
                                                 &    Allocate memory \\
`void *calloc(size_t nmemb, size_t size)`         &    `int  m_create(int len, int width)`   \\
\hline
                                                 &    Free memory \\
`void free(void *ptr}`                            &    `void m_free(int m)` \\
\hline

        & Pointer to element in list \\
        & `void *mls(int m, int pos)`\\
          \cline{2-2}
        &    Append *d to end of list \it{m} \\
        &    `int m_put(int m, void *d);` \\
          \cline{2-2}
        & Get length of list \\
        & `int m_len(int m)` \\
          \cline{2-2}
        & Set length of list to Zero, i.e. clear \\
        & `int m_clear(int m)` \\
          \cline{2-2}
        & Change length of list \\
        & `int m_setlen(int m, int len)` \\
\hline
& Using Strings \\
`int asprintf(char **s,char *fmt, ...)`    &

\begin{minipage}[t]{0.5\textwidth}
\begin{Verbatim}
int s_printf(int m,
  int p, char *fmt, ...);

int str;
/* create a string */
str = s_printf(0,0, "Hello." );
/* append/resize */
s_printf(str,-1,
  "Last until: %d", 2038 );
/* insert 6 bytes at 5 */
m_ins(str,5,6);
/* memcpy */
m_write( str, 5,
  " World", 6);

\end{Verbatim}
\end{minipage}
\\

\hline
 & Sorting Arrays \\
\hline
\multicolumn{2}{|c|}{
{\small typedef int (*cmp\_t)(void *a,void *b)}
}\\

\begin{minipage}[t]{0.5\textwidth}
\begin{Verbatim}
void qsort(void *base, size_t nmemb,
size_t size,
cmp_t cmp )
\end{Verbatim}
\end{minipage}

&

\begin{minipage}[t]{0.5\textwidth}
\begin{Verbatim}
m_qsort(int m,int cmp_t cmp)
{
   qsort( m_buf(m),
          m_len(m),
          m_width(m),
          cmp );
}

\end{Verbatim}
\end{minipage}


\\
\hline
\begin{minipage}[t]{0.5\textwidth}
\begin{Verbatim}
void *lsearch(void *key, void *base,
size_t *nmemb,
size_t size, cmp_t cmp)
\end{Verbatim}
\end{minipage}
&
\begin{minipage}[t]{0.5\textwidth}
\begin{Verbatim}
int m_lsearch(void *k,int m,
cmp_t cmp)
{
  int p; void *a;
  m_foreach(m,p,a)
    if(!cmp(a,k)) return p;
  return m_put(m,k);
}

\end{Verbatim}
\end{minipage}
\\
\hline


\end{tabular}
\end{figure}

%% ---------------------------------------------------------





%% ---------------------------------------------------------

\begin{figure}\caption{simple mls usage}
\begin{tabular}{|l|l|}
\hline
\multicolumn{2}{|c|}{Examples} \\
 \hline

\begin{minipage}[t]{0.5\linewidth}
\begin{Verbatim}
Args arg[10];
int cnt=0;
arg[cnt]=data[0]; cnt++;
arg[cnt]=data[1]; cnt++;
set_args(arg,cnt);


\end{Verbatim}
\end{minipage}

&

\begin{minipage}[t]{0.5\textwidth}
\begin{Verbatim}
int arg;
arg=m_create(10,sizeof(Args));
m_put(args,data+0);
m_put(args,data+1);
set_args(arg);
\end{Verbatim}
\end{minipage}

\\
\hline

\begin{minipage}[t]{0.4\textwidth}
\begin{Verbatim}
struct dbase *findEntry(
  struct dbase *ctx, int max,
  char *s )
{
  int i;
  for(i=0;i<max;i++)
    if( strcmp(ctx[i].key,s)==0 )
      return ctx+i;
  return NULL;
}


\end{Verbatim}
\end{minipage}

&

\begin{minipage}[t]{0.5\textwidth}
\begin{Verbatim}
struct dbase *findEntry(int ctx,
  char *s)
{
  int i;
  struct dbase *db;
  for(i=0;i< m_len(ctx); i++) {
    db = mls(ctx,i);
    if( strcmp(db->key, s)==0 )
      return db;
  }
  return NULL;
}
\end{Verbatim}
\end{minipage}
\\
\hline


&
\begin{minipage}[t]{0.5\textwidth}
\begin{Verbatim}
struct dbase *findEntry(int ctx,
  char *s)
{
  int i;
  struct dbase *db;
  i=m_lookup_str(ctx,s,1);
  db = i < 0 ? NULL : mls(ctx,i);
  return db;
}
\end{Verbatim}
\end{minipage}
\\
\hline



\begin{minipage}[t]{0.4\textwidth}
\begin{Verbatim}
char *concat(char *s1, char *s2)
{
  int l2 = strlen(s2)+1;
  int l1 = strlen(s1);
  s1 = realloc( s1, l1+l2 );
  memcpy( s1, l1, s2, l2 );
  return s1;
}


\end{Verbatim}
\end{minipage}

&


\begin{minipage}[t]{0.5\textwidth}
\begin{Verbatim}
int concat(int s1, char *s2)
{
  m_write(s1,
          m_len(s1)-1,
          s2, strlen(s2));
}
/* no need to return s1 */
/* s1 does not change */
/* on realloc */
\end{Verbatim}
\end{minipage}

\\
\hline

\end{tabular}
\end{figure}



\end{document}
